package hh.leecode.binarytree;

import java.net.URLClassLoader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *
 */
public class 二叉树_后序遍历 {
    public static void main(String[] args) {

        TreeNode root = TreeNode.createDefaultTree(1);
        ArrayList<Object> list = new ArrayList<>();
        after_order_recursion(root, list);
        System.out.println(list);

        list = new ArrayList<>();
        after_order_断子绝孙法(root, list);
        System.out.println(list);
    }


    /**
     * 递归法
     * <p>
     * 先左，再中，再右
     */
    private static void after_order_recursion(TreeNode root, List<Object> list) {
        if (root == null) return;

        if (root.left != null) after_order_recursion(root.left, list);
        if (root.right != null) after_order_recursion(root.right, list);
        list.add(root.val);
    }


    /**
     * 断子绝孙法
     * 重点就是，add后一定要断开跟parent的引用
     */
    private static void after_order_断子绝孙法(TreeNode root, List<Object> list) {
        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode peek = stack.peek();

            if (peek.right == null && peek.left == null) {
                list.add(stack.pop().val);
                continue;
            }

            if (peek.right != null) {
                stack.push(peek.right);
                peek.right = null;
            }
            if (peek.left != null) {
                stack.push(peek.left);
                peek.left = null;
            }
        }
    }


    private static void after_order_多节点记录_my(TreeNode root, List<Object> list) {

        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        TreeNode curr = root;
        TreeNode prev = null;

        while (!stack.isEmpty()) {

            curr = stack.peek();

            if (prev == null || prev.left == curr || prev.right == curr) { //down
                if (curr.left != null) {
                    stack.push(curr.left);
                } else if (curr.right != null) {
                    stack.push(curr.right);
                }
            } else if (curr.left == prev) { // 回退，右节点考虑
                if (curr.right != null) stack.push(curr.right);
            }else {
                list.add(curr.val);
                stack.pop();
            }
            prev = curr;

        }


    }

    /**
     * @param root
     * @param list
     */
    private static void after_order_多节点记录(TreeNode root, List<Object> list) {
        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        TreeNode curr = null;
        TreeNode prev = null;

        while (!stack.empty()) {

            curr = stack.peek();
            if (prev == null || prev.left == curr || prev.right == curr) { // down the tree
                if (curr.left != null) {
                    stack.push(curr.left);
                } else if (curr.right != null) {
                    stack.push(curr.right);
                }

            } else if (curr.left == prev) { // up from left
                if (curr.right != null) {
                    stack.push(curr.right);
                }
            } else { // 无法 down ，或者已经down 过了，就需要add了
                list.add(curr.val);
                stack.pop();
            }


            prev = curr;


        }


    }


}
